package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/04
 */
public class Test0403_01 {

    /**
     * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
     *
     * 示例 1：
     *
     * 输入：x = 2.00000, n = 10
     * 输出：1024.00000
     * 示例 2：
     *
     * 输入：x = 2.10000, n = 3
     * 输出：9.26100
     * 示例 3：
     *
     * 输入：x = 2.00000, n = -2
     * 输出：0.25000
     * 解释：2-2 = 1/22 = 1/4 = 0.25
     *
     *
     * 提示：
     *
     * -100.0 < x < 100.0
     * -231 <= n <= 231-1
     * -104 <= xn <= 104
     *
     * 刷了两遍，每次看到都不会做，今天终于理解了。x是底数，n是指数，ans是结果，
     * x^n代表的是一个数值，快速幂说白了就是在确保数值不变的情况下，用二分法把数值从指数不断地往底数里面搬。
     * 核心是n=n/2, x=x^2这两句代码。但是由于指数可能是奇数，整数除二会丢失一位底数，所以要在ans里面记录奇数轮丢失的底数。
     *
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        //将正数n和负数n都给转换为正数n
        //注意：Java 代码中 int32 变量n∈[−2147483648,2147483647]
        //因此当 n = -2147483648 时执行 n = -n 会因越界而赋值出错
        //我们此处一开始就把 n 用 long 存储
        long b = n;

        if (n < 0) {
            b = -b;
            x = 1 / x;
        }
        return culc(x, b);
    }

    //快速幂模版
    //递归的进行x的n次方计算
    public double culc(double base, long power) {

        double res = 1.0;

        while (power > 0) {
            //两种情况会进入if语句：
            //1.幂次若为奇数，提前多乘一次x
            //2.当幂次除到1，把x赋值给res
            if ((power & 1) == 1) {
                res *= base;
            }

            //幂次除以2
            power = power >> 1;

            //底数平方
            base = base * base;
        }
        return res;
    }


    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
